package com.sheng.leetcode.year2022.month09.day18;

import org.junit.Test;

import java.util.HashSet;
import java.util.Set;

/**
 * @author liusheng
 * @date 2022/09/19
 *<p>
 * 827. 最大人工岛<p>
 *<p>
 * 给你一个大小为 n x n 二进制矩阵 grid 。最多 只能将一格0 变成1 。<p>
 * 返回执行此操作后，grid 中最大的岛屿面积是多少？<p>
 * 岛屿 由一组上、下、左、右四个方向相连的1 形成。<p>
 *<p>
 * 示例 1:<p>
 * 输入: grid = [[1, 0], [0, 1]]<p>
 * 输出: 3<p>
 * 解释: 将一格0变成1，最终连通两个小岛得到面积为 3 的岛屿。<p>
 *<p>
 * 示例 2:<p>
 * 输入: grid = [[1, 1], [1, 0]]<p>
 * 输出: 4<p>
 * 解释: 将一格0变成1，岛屿的面积扩大为 4。<p>
 *<p>
 * 示例 3:<p>
 * 输入: grid = [[1, 1], [1, 1]]<p>
 * 输出: 4<p>
 * 解释: 没有0可以让我们变成1，面积依然为 4。<p>
 *<p>
 * 提示：<p>
 *<p>
 * n == grid.length<p>
 * n == grid[i].length<p>
 * 1 <= n <= 500<p>
 * grid[i][j] 为 0 或 1<p>
 *<p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/making-a-large-island">...</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode0827 {

    @Test
    public void test01() {
        int[][] grid = {{1, 0}, {0, 1}};
//        int[][] grid = {{1, 1}, {1, 0}};
//        int[][] grid = {{1, 1}, {1, 1}};
        System.out.println(new Solution().largestIsland(grid));
    }
}
//class Solution {
//    public int largestIsland(int[][] grid) {
//        int n = grid.length;
//        return 0;
//    }
//}

//并查集 + 枚举
//为了方便，我们令 grid 为 g。
//根据题意，容易想到通过「并查集」来维护所有连通块大小，再通过「枚举」来找最优翻转点。
//具体的，我们可以先使用「并查集」维护所有 g[i][j] = 1 的块连通性，
//并在维护连通性的过程中，使用 sz[idx] 记录下每个连通块的大小（注意：只有连通块根编号，
//sz[idx] 才有意义，即只有 sz[find(x)] 才有意义）。
//随后我们再次遍历 g，根据原始的 g[i][j] 的值进行分别处理：
//若 g[i][j] = 1，该位置不会作为翻转点，但真实最大面积未必是由翻转后所导致的（可能取自原有的连通块），
//因此我们需要将 sz[root] 参与比较，其中 root 为 (i, j) 所属的连通块根节点编号；
//若 g[i][j] = 0，该位置可作为翻转点，
//我们可以统计其四联通位置对应的连通块大小总和 tot（注意若四联通方向有相同连通块，只统计一次），
//那么 tot + 1 即是翻转该位置所得到的新连通块大小。
//最后对所有连通块大小取最大值即是答案。
//一些细节：为了方便，我们令点 (i, j) 的编号从 1 开始；
//同时由于我们本身就要用 sz 数组，因此我们可以随手把并查集的「按秩合并」也加上。体现在 union 操作时，
//我们总是将小的连通块合并到大的连通块上，从而确保我们并查集单次操作即使在最坏情况下复杂度仍为 O(\alpha(n))O(α(n))（可看作常数）。
//需要注意只有同时应用「路径压缩」和「按秩合并」，并查集操作复杂度才为 O(\alpha(n))O(α(n))。
//
class Solution {
    static int N = 510;
    static int[] p = new int[N * N], sz = new int[N * N];
    // 上下左右
    int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
    int find(int x) {
        if (p[x] != x) {
            p[x] = find(p[x]);
        }
        // p[x] 的值与 x 一致时返回
        return p[x];
    }
    void union(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) {
            return ;
        }
        if (sz[ra] > sz[rb]) {
            union(b, a);
        } else {
            sz[rb] += sz[ra]; p[ra] = p[rb];
        }
    }
    public int largestIsland(int[][] g) {
        // 二维数组长宽
        int n = g.length;
        for (int i = 1; i <= n * n; i++) {
            p[i] = i; sz[i] = 1;
        }
        // 循环二维数组
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                // 该坐标位置为0时，是海洋位置，跳过
                if (g[i][j] == 0) {
                    continue;
                }
                // 该坐标是陆地，循环dirs上下左右进行移动
                for (int[] di : dirs) {
                    int x = i + di[0], y = j + di[1];
                    // 如果进行移动后超出了边界，或者移动之后是海洋则跳过
                    if (x < 0 || x >= n || y < 0 || y >= n || g[x][y] == 0) {
                        continue;
                    }
                    union(i * n + j + 1, x * n + y + 1);
                }
            }
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (g[i][j] == 1) {
                    ans = Math.max(ans, sz[find(i * n + j + 1)]);
                } else {
                    int tot = 1;
                    Set<Integer> set = new HashSet<>();
                    for (int[] di : dirs) {
                        int x = i + di[0],y = j + di[1];
                        if (x < 0 || x >= n || y < 0 || y >= n || g[x][y] == 0) {
                            continue;
                        }
                        int root = find(x * n + y + 1);
                        if (set.contains(root)) {
                            continue;
                        }
                        tot += sz[root];
                        set.add(root);
                    }
                    ans = Math.max(ans, tot);
                }
            }
        }
        return ans;
    }
}
//
//作者：AC_OIer
//链接：https://leetcode.cn/problems/making-a-large-island/solution/by-ac_oier-1kmp/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
